[정렬] 선택정렬
정렬
| 정렬 알고리즘 | 정의 | 시간복잡도 |
|---|
| 삽입 | 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 | O(N) ~ O(N^2) |
| 버블 | 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 | O(N^2) |
| 선택 | 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 | O(N^2) |
| 퀵 | pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 | O(NlogN) ~ O(N^2) |
| 힙 | 이진트리를 이용하여 최대힙(오름차순)/최소힙(내림차순) 트리를 구성해정렬하는 방식 | O(NlogN) |
| 병합 | 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 | O(NlogN) + 추가적인 메모리 필요 |
| 기수 | 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 | O(N) + 추가적인 메모리 필요 |
선택정렬이란?
선택정렬은 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법입니다.
선택정렬은 구현 방법이 복잡하고, 시간복잡도도 O(N^2)으로 효율적이지 않습니다.
(코딩테스트에서는 직접적인 문제로 출제되지 않는 편)
선택정렬 과정
- 1, 3, 4, 2, 5 를 선택정렬로서 정렬하기
- 빨간색 : 정렬이 완료된 숫자
- 파란색 : 정렬을 해야할 숫자
| 순번 | 과정 | 과정 | 과정 | 과정 | 과정 |
|---|
| 첫번째 | 1 | 3 | 4 | 2 | 5 |
| 두번째 | 1 | 2 | 4 | 3 | 5 |
| 세번째 | 1 | 2 | 3 | 4 | 5 |
| 완성 | 1 | 2 | 3 | 4 | 5 |
- 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다
- 남은 정렬 부분에서 가장 앞에있는 데이터와 선택된 데이터를 swap 한다
- 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소한다
- 전체 데이터 크기만큼 index가 커질 때까지 , 즉 남은 정렬 부분이 없을 때까지 반복한다
선택정렬 구현
- 두번째 반복문에서, 정렬해야하는 범위에서 최솟값 인덱스를 찾는다
- 범위에서 가장 앞에있는 인덱스와 최솟값 인덱스가 다르다면, swap()을 진행한다
- 정렬이 완료된 후, 출력
public class App {
private static final int SIZE = 5;
public static void main(String[] args) throws Exception {
int []arr = {1,3,4,2,5};
for(int i =0; i<SIZE; i++){
int minIdx = i;
for(int j = i+1; j< SIZE; j++){
if (arr[minIdx] > arr[j]){
minIdx = j;
}
}
if(i != minIdx){
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
for (int i : arr) {
System.out.println(i);
}
}
}
관련 문서